package leetcodeHis.链表;

/**
 * 怎么找到倒数第n个节点
 *
 * 1. 倒数n是怎么判断，正向扫描总节点数，然后再扫描一次到  sum - n
 *
 * 2.
 */
public class Algo_19_删除倒数第N个节点 {

    public  static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next  = head;
        int sum = 0;
        ListNode index = head;
        while (index!=null) {
            sum++;
            index = index.next;
        }

        int zhishi = 0;
        ListNode first = dummy;
        while (first != null) {
            if(zhishi == sum -n) {
                first.next = first.next.next;
                break;
            }
            zhishi++;
            first = first.next;
        }

        return  dummy.next;
    }

    //两个指针，一个先走n步
    public  static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode slow = head;
        ListNode quick = head;

        for (int i = 0; i < n; i++) {
            quick = quick.next;
        }

        if(quick == null) {
            return head.next;
        }

        while (quick.next!=null) {
            slow = slow.next;
            quick = quick.next;
        }
        slow.next = slow.next.next;

        return head;
    }



    public static void main(String[] args) {
        ListNode b = new ListNode(1);
        b.next = new ListNode(2);
        b.next.next = new ListNode(3);
        b.next.next.next = new ListNode(4);
        b.next.next.next.next = new ListNode(5);

        ListNode result = removeNthFromEnd2(b, 2);
        while (result!=null) {
            System.out.print(result.val + "-");
            result = result.next;
        }
    }
}
